package SortAlgorithm;

import com.alibaba.fastjson.JSON;

import java.util.Random;

public class MySortExercise {

    /**
     * 定一个下标,然后排序两边
     */
    //请书写一个倒序的快速排序算法
    static class FastSort {

        private Random random = new Random();

        public void fastSort(int[] arr) {
            this.dfs(arr, 0, arr.length - 1);
        }

        //递归左右划分
        private void dfs(int[] arr, int left, int right) {

            if (left >= right) {
                return;
            }

            int randomIndex = this.random.nextInt(right - left + 1) + left;
            this.swap(arr, left, randomIndex);

            int index = this.itemSort(arr, left, right);

            this.dfs(arr, left, index);
            this.dfs(arr, index + 1, right);

        }

        //使中间数有意义
        private int itemSort(int[] arr, int left, int right) {

            while (left < right) {

                //从右边找一个比当前元素小的元素
                while (left < right && arr[right] >= arr[left]) {
                    right--;
                }

                this.swap(arr, left, right);

                //从左边找一个比当前元素大的元素
                while (left < right && arr[left] <= arr[right]) {
                    left++;
                }

                this.swap(arr, left, right);
            }

            return left;
        }

        //swap方法
        private void swap(int[] arr, int left, int right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }

    }

    /**
     * (分割)切割数组,切成最细,然后开始合并
     * (合并)利用新创建数组,将元素放入,放入时要按照顺序放入;
     */
    //请书写一个归并排序算法
    static class MergeSort {

        private void mergeSort(int[] arr) {
            int[] tempArr = new int[arr.length];
            this.dfsSplit(arr, tempArr, 0, arr.length - 1);
        }

        // 递归切割,然后排序
        private void dfsSplit(int[] arr, int[] tempArr, int left, int right) {

            if (left >= right) {
                return;
            }

            int mid = (right - left) / 2 + left;
            this.dfsSplit(arr, tempArr, left, mid);
            this.dfsSplit(arr, tempArr, mid + 1, right);
            this.partSort(arr, tempArr, left, right);
        }

        private void partSort(int[] arr, int[] tempArr, int left, int right) {

            if (left == right) {
                return;
            }

            int mid = (right - left) / 2 + left;

            // 本有序,不用排
            if (arr[mid] <= arr[mid + 1]) {
                return;
            }

            int sortIndex = left;
            int sortLeft = left;
            int sortRight = mid + 1;

            // 将temp成为有序数组
            while (sortLeft <= mid && sortRight <= right) {
                if (arr[sortLeft] <= arr[sortRight]) {
                    tempArr[sortIndex++] = arr[sortLeft++];
                } else {
                    tempArr[sortIndex++] = arr[sortRight++];
                }
            }

            // 左边剩余
            while (sortLeft <= mid) {
                tempArr[sortIndex++] = arr[sortLeft++];
            }

            // 右边剩余
            while (sortRight <= right) {
                tempArr[sortIndex++] = arr[sortRight++];
            }

            // 填充原数组
            for (int i = left; i <= right; i++) {
                arr[i] = tempArr[i];
            }

        }

    }

    private static int[] getArr() {
        int[] sourceArr = {4, 5, 1, 2, 5, 46, 362, 3, 62, 35, 12, 41, 35, 35, 36, 3, 134135, 513, 55, 3616, 316, 12231};
        int[] arr = new int[sourceArr.length];
        System.arraycopy(sourceArr, 0, arr, 0, arr.length);
        return arr;
    }

    public static void main(String[] args) {
//        int[] arr = getArr();
        int[] arr = new int[]{2, 4, 3, 5, 1};
        MergeSort2 mergeSort2 = new MergeSort2();
        mergeSort2.mergeSort(arr);
        System.out.println(JSON.toJSONString(arr));
    }

    static class FastSort2 {
        private Random random = new Random();

        // 快速排序练习-2
        public void fastSort(int[] arr) {
            this.split(arr, 0, arr.length - 1);
        }

        // 找到中间的那个元素,然后分割
        private void split(int[] arr, int left, int right) {

            if (left >= right) {
                return;
            }

            int baseIndex = this.random.nextInt(right - left + 1) + left;
            this.swap(arr, left, baseIndex);

            int mid = this.getMid(arr, left, right);
            this.split(arr, left, mid);
            this.split(arr, mid + 1, right);
        }

        // 找到中间的那个元素所在的下标
        private int getMid(int[] arr, int left, int right) {

            while (left < right) {

                // 从右边找一个比当前元素小的元素
                while (left < right && arr[right] >= arr[left]) {
                    right--;
                }
                this.swap(arr, left, right);

                // 从左边找一个比当前元素大的元素
                while (left < right && arr[left] <= arr[right]) {
                    left++;
                }
                this.swap(arr, left, right);

            }

            return left;
        }

        private void swap(int[] arr, int index1, int index2) {
            int temp = arr[index1];
            arr[index1] = arr[index2];
            arr[index2] = temp;
        }
    }

    // 剑指offer51题
    static class MergeSort2 {

        public void mergeSort(int[] arr) {
            int count = this.dfs(arr, new int[arr.length], 0, arr.length - 1);
            System.out.println(count);
        }

        // 先递归到一个元素,再进行排序
        private int dfs(int[] arr, int[] temp, int left, int right) {
            if (left >= right) {
                return 0;
            }

            int mid = (right - left) / 2 + left;
            int leftCount = this.dfs(arr, temp, left, mid);
            int rightCount = this.dfs(arr, temp, mid + 1, right);
            int count = this.sort(arr, temp, left, right);
            return leftCount + rightCount + count;
        }

        private int sort(int[] arr, int[] temp, int left, int right) {

            if (left == right) {
                return 0;
            }

            int mid = (right - left) / 2 + left;

            if (arr[mid] <= arr[mid + 1]) {
                return 0;
            }

            int count = 0;

            int index = left;
            int l = left;
            int r = mid + 1;

            while (l <= mid && r <= right) {
                if (arr[l] <= arr[r]) {
                    temp[index++] = arr[l++];
                } else {
                    // 现在进右,那么左边剩余的,比现在右边进去的大
                    count += ((mid + 1) - l);
                    temp[index++] = arr[r++];
                }
            }

            while (l <= mid) {
                temp[index++] = arr[l++];
            }

            while (r <= right) {
                temp[index++] = arr[r++];
            }

            for (int i = left; i <= right; i++) {
                arr[i] = temp[i];
            }

            return count;
        }

    }

}
